/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-20
 * Time: 22:25
 */

/**
 * dp
 */
public class Solution {
    public int maximalSquare(char[][] matrix) {
        int row=matrix.length;
        int col=matrix[0].length;
        int maxLen=0;//记录最大正方形的边长
        int[][] dp=new int[row][col];
        //第一行和第一列都可以直接确定
        for(int i=1;i<col;i++){
            if(matrix[0][i]=='0'){
                dp[0][i]=0;
            }else{
                dp[0][i]=1;
                maxLen=1;
            }
        }
        for(int i=0;i<row;i++){
            if(matrix[i][0]=='0'){
                dp[i][0]=0;
            }else{
                dp[i][0]=1;
                maxLen=1;
            }
        }
        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                if(matrix[i][j]=='0'){
                    dp[i][j]=0;//dp[i][j]表示以该位置为左下角的最大正方形的边长
                }else{
                    //dp[i][j]由上边,左边,左上边的最小值确定
                    dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    maxLen=Math.max(dp[i][j],maxLen);
                }
            }
        }
        return maxLen*maxLen;
    }
}
